//数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 3
//输出：["((()))","(()())","(())()","()(())","()()()"]
// 
//
// 示例 2： 
//
// 
//输入：n = 1
//输出：["()"]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 8 
// 
// Related Topics 字符串 动态规划 回溯 
// 👍 2667 👎 0


package com.cjl.leetcode.editor.cn;

import java.util.*;
import java.util.stream.Collectors;

/**
 * [P22]_括号生成
 *
 * @author cjl
 * @date 2022-05-30 23:01:41
 */
public class P22_GenerateParentheses {
    public static void main(String[] args) {
        //测试代码
        Solution solution = new P22_GenerateParentheses().new Solution();
        solution.generateParenthesis(3).stream().forEach(s -> System.out.println("args = " + s));

    }

    //力扣代码
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 解题思路：遍历
         * 第一位只有（一种放法，第二位有两种放法，第三位有两种放法，每种放完判断s是否满足条件
         *
         * @param n
         * @return
         */
        public List<String> generateParenthesis(int n) {
            Map<String, Integer> map = new HashMap<>();
            map.put("(", 1);
            for (int i = 1; i < n * 2; i++) {
                Map<String, Integer> tmpMap = new HashMap<>();
                for (String sb : map.keySet()) {
                    int leftNum = map.get(sb); //代表左括号数
                    //左括号总数小于n，可以加左括号
                    if (leftNum < n) {
                        String sb1 = sb + ("(");
                        tmpMap.put(sb1, leftNum + 1);
                    }
                    //说明左括号小于等于有括号，不可以添加有括号
                    if (sb.length() < 2 * leftNum) {
                        String sb2 = sb + ("）");
                        tmpMap.put(sb2, leftNum);
                    }
                }
                if (tmpMap.keySet().size() != 0) {
                    map = tmpMap;
                }

            }
            return map.keySet().stream().collect(Collectors.toList());
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}